package com.ly.algorithm.leetcode.backtracking;



/**
 * @Classname Problem37
 * @Description
 *
 * * 编写一个程序，通过已填充的空格来解决数独问题。
 *  *
 *  * 一个数独的解法需遵循如下规则：
 *  *
 *  * 数字 1.txt-9 在每一行只能出现一次。
 *  * 数字 1.txt-9 在每一列只能出现一次。
 *  * 数字 1.txt-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
 *  * 空白格用 '.' 表示。
 *  *
 *  *
 *  *
 *  * 一个数独。
 *  *  5 3 .  . 7 .  . . .
 *  *  6 . .  1.txt 9 5  . . .
 *  *  . 9 8  . . . . 6 .
 *  *  ...................
 *  *
 *  * 答案被标成红色。
 *  *
 *  * Note:
 *  *
 *
 * @Date 2020/12/25 16:17
 * @Author 冷心影翼
 */
public class Problem37 {

	public static void main(String[] args) {
		Solution37 solution37 = new Solution37();
		char[][] board = {
			{'5','3','.','.','7','.','.','.','.'},
			{'6','.','.','1','9','5','.','.','.'},
			{'.','9','8','.','.','.','.','6','.'},
			{'8','.','.','.','6','.','.','.','3'},
			{'4','.','.','8','.','3','.','.','1'},
			{'7','.','.','.','2','.','.','.','6'},
			{'.','6','.','.','.','.','2','8','.'},
			{'.','.','.','4','1','9','.','.','5'},
			{'.','.','.','.','8','.','.','7','9'}};
		solution37.solveSudoku(board);
		for(int i=0;i<9;i++) {
			for (int j=0;j<9;j++) {
				System.out.print(board[i][j]+" ");
			}
			System.out.println();
		}
	}
}

class Solution37 {
	public void solveSudoku(char[][] board) {
		backTracking(board,0,0);
	}

	public boolean backTracking(char[][] board,int n,int m) {
		if(n == 9)
			return true;
		if(m == 9) {
			return backTracking(board,n+1,0);
		}
		if(board[n][m]!='.') {
			return backTracking(board,n,m+1);
		}
		for (char i = '1'; i <= '9'; i++) {
			if(!isValid(board,n,m,i)) {
				continue;
			}
			board[n][m] = i;
			if(backTracking(board,n,m+1))
				return true;
			board[n][m] = '.';
		}
		return false;
	}

	public boolean isValid(char[][] board,int n,int m,char v) {
		for (int i = 0; i < 9; i++) {
			if(board[n][i] == v )
				return false;
			if(board[i][m] == v )
				return false;
			// 判断 3 x 3 方框是否存在重复
			int x = (n/3)*3 + i/3;
			int y = (m/3)*3 + i%3;
			if (board[x][y] == v)
				return false;
		}
		return true;
	}
}